package com.sxj.myleetcode.march;

import java.util.Arrays;
import java.util.List;

/**
 * @ProjectName: myleetcode
 * @Package: com.sxj.myleetcode
 * @ClassName: Main
 * @Author: sxj
 * @Description:
 * @Date: 2024/3/11 9:43
 * @Version: 1.0.0
 */
public class BinarySummation0311 {

    public static void main(String[] args) {
//        String a = "11";
//        String b = "1";
//        String s = getBinarySummation(a, b);
//        System.out.println(s);
//
//        String s2 = getBinarySummationV2(a, b);
//        System.out.println(s2);

//        int num = 1;
//        int squreRoot = getSquereV2(num);
//        System.out.println(squreRoot);

        //1 斐波那契算法：f(n) = f(n-1) + f(n-2) n>=2
        int febo = getFebo(6);
        System.out.println(febo);
    }


    public static void test(){
        int[] a = {1,1,2};
        //去重重复数据
//        创建一个辅助标记数组，用于标记每个元素是否已经出现过。
//        遍历原始数组，对于每个元素，检查在标记数组中对应位置的标记，如果未标记，则将该元素输出，并标记对应位置。
//        最后得到的结果数组即为去重后的数组。

        boolean[] seen = new boolean[a.length];
        for (int i = 0; i < a.length; i++) {
            int i1 = a[i];

        }

    }


    /**
     * Climb Stairs
     * @param n
     */
    public static int getFebo(int n){
        if (n < 2){
            return 1;
        }
        int a = 1;
        int b = 1;
        for (int i = 2; i <= n ; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }

    /**
     * 查找平方根
     * @param num
     */
    public static int getSquereV2(int num){
        if (num == 0 || num == 1){
            return num;
        }
        double squereRootV2 = getSquereRootV2(num, num / num);
        return (int) squereRootV2;
    }

    /**
     * 查找平方根
     * @param num
     */
    public static double getSquereRootV2(int num,double x){
        double res = (x + num/x )/2;
        if (res == x){
            return x;
        }else {
            return getSquereRootV2(num,res);
        }
    }

    /**
     * 查找平方根
     * @param num
     */
    public static int getSquere(int num){
        double squreRoot = getSqureRoot(num, num / 2); //TODO 第一次的guess值如何确定
        System.out.println("根是： "+squreRoot);
        return (int)squreRoot;
    }

    /**
     * 查找平方根
     * @param num
     * @param guess
     */
    public static double getSqureRoot(int num,double guess){
        if (num == 0 || num == 1){
            return num;
        }
        //1 比较 猜测值 和 平均数的 接近程度
        double abs = Math.abs(guess - num / guess);
        if (abs < 0.00001){ //TODO 这个值如何确定
            return guess;
        }

        guess = (guess + num/guess) /2;
        return getSqureRoot(num,guess);

    }

    //TODO: 还是不对，需要修改
    /**
     * 二进制求和：给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
     * @param a
     * @param b
     */
    public static String getBinarySummation(String a,String b){
        StringBuffer sb = new StringBuffer();
        char[] aChars = a.toCharArray();
        char[] bChars = b.toCharArray();
        int carry=  (aChars[aChars.length - 1] - '0') & (bChars[bChars.length - 1] - '0');
        for (int i = aChars.length - 1 ,j= bChars.length - 1; i >= 0 || j >= 0; i--,j--) {
            //和： a 异或 b 异或 进位
            int sum = (i>=0 ? aChars[i] - '0' : 0) ^ (j >= 0? bChars[j] - '0' : 0);
            carry = carry & (i>=0 ? aChars[i] - '0' : 1) & (j >= 0? bChars[j] - '0' : 1) ;
            sb.append(sum);
        }
        if (carry >0){
            sb.append(carry);
        }
        // 从最后一位开始计算，需要进行翻转
        sb.reverse();
        return sb.toString();
    }

    /**
     * 二进制求和：给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
     * @param a
     * @param b
     */
    public static String getBinarySummationV2( String a,String b){
        StringBuffer sb = new StringBuffer();
        int carry = 0;  //设置进位
        for (int i = a.length()-1,j = b.length()-1; i >= 0 | j >= 0; i--, j--) {
            //从最后一位开始计算，记得结果要进行一次翻转
            //和： （a + b+ 进位）%2
            //进位：（a + b + 进位）/2
            int sum = carry;
            sum += i >=0 ? a.charAt(i) - '0'  : 0; //最重要的点是 减去0
            sum += j >=0 ? b.charAt(j) - '0' : 0;
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry >0){
            sb.append(carry);
        }
        //进行翻转
        sb.reverse();
        return sb.toString();
    }
}
